import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Text {
    public static void main(String[] args) {
        int[] array = {57,43,74,24,95,2,16,38};
        quickSortNor(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            boolean flag = false;
            for(int j = 0; j < array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    flag = true;
                    swap(array,j,j+1);
                }
            }
            if(flag){
                break;
            }
        }
    }

// 快速
    public static void quickSort(int[] array){
        quickChild(array,0,array.length-1);
    }
    private static int findMid(int[] array,int left,int right,int mid){
        if(array[left]>array[right]){
            if(array[mid] >array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > right){
                return right;
            }else if(array[mid] < array[left]){
                return left;
            }else{
                return mid;
            }
        }
    }
    public static void quickChild(int[] array,int left,int right){
        if(left >= right) {
            return;
        }
        int mid = (left+right)/2;
        int midNum = findMid(array,left,right,mid);
        swap(array,left,midNum);
        int povit =  quick(array,left,right);
        quickChild(array,left,povit-1);
        quickChild(array,povit+1,right);
    }
    public static int quick(int[] array,int start,int end){
        int i = start;
        int j = end;
        int tmp = array[start];
        while(i<j){
            while(i<j && array[j] >= tmp){
                j--;
            }
            array[i] = array[j];
            while(i<j && array[i] <= tmp){
                i++;
            }
            array[j] = array[i];
        }
        array[i] = tmp;
        return i;
    }
    //快排非递归
    public static void quickSortNor(int[] array,int left,int right){
        Deque<Integer> stack = new LinkedList<>();
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()){
            int end = stack.poll();
            int start = stack.poll();
            int provt = quick(array,start,end);
            if(end-1 > provt){
                stack.push(provt+1);
                stack.push(end);
            }
            if(start+1 < provt){
                stack.push(start);
                stack.push(provt-1);
            }
        }

    }

}
